#include <stdio.h>
#define MAX 100
#define MAXCOST 0x7fffffff

int graph[MAX][MAX];
int isAdd(int in,int add,int mst[],int n){
	if(mst[in]!=0&&mst[add]!=0)
		return 0;
	if(mst[in]==0&&mst[add]==0)
		return 1;
	if(mst[in]==0){
		for (int i = 1; i <= n; ++i)
		{
			if(mst[i]==in)
				return 0;
		}
	}else{
		for (int i = 1; i <= n; ++i)
		{
			if(mst[i]==add)
				return 0;
		}
	}
	return 1;
}
void kruskal(int graph[][MAX],int n){

	int mst[MAX] ;
	int sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		mst[i] = 0;
	}

	for(int k = 0 ; k < n-1; ++k){
		int min = MAXCOST;
		int nowNode = 0;
		int addNode = 0;
		for (int i = 1; i < n; ++i)
		{
			for(int j = i + 1; j <= n; ++j){
				if(graph[i][j] < min && isAdd(i,j,mst,n)==1){
					min = graph[i][j];
					nowNode = i;
					addNode = j;
				}
			}
		}
		if(addNode!=0){
			if(mst[addNode]==0)
				mst[addNode] = nowNode;
			else
				mst[nowNode] = addNode;
			sum += min;
			printf("%d-%d-%d\n",nowNode,addNode,min);
		}
	}
	printf("sum = %d\n",sum);
}
void display(int graph[][MAX],int n){
	printf("您输入的矩阵是：\n");
	for (int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n ; ++j){
			if(graph[i][j]==MAXCOST){
				printf("@ ");
				continue;
			}
			printf("%d ",graph[i][j]);
		}
		printf("\n");
	}
}
int main(){
	int i, j , k , m , n;
	int x, y, cost;
	scanf("%d%d",&m,&n);
	for(i = 1; i <= m; i ++){
		for(j = 1; j <= m; j++){
			graph[i][j] = MAXCOST;
		}
	}
	for(k = 1; k <= n; k++){
		scanf("%d%d%d",&i,&j,&cost);
		graph[i][j] = cost;
		graph[j][i] = cost;
	}
	display(graph,m);
	kruskal(graph,m);	
	return 0;

}